﻿#include "stdafx.h"
#include "LongestPalindrome.h"

using namespace std;

namespace algorithm {
std::string CLongestPalindrome::From(std::string s)
{
    auto len = s.length();
    if (len <= 1) {
        return s;
    }
    bool* dp = new bool[len * len] {};
    size_t begin = 0;
    size_t maxlen = 1;
    /* 从小到大枚举指定长度的字符串，因为更长的回文字符串判断会用到短的字符串 */
    for (size_t count = 1; count <= len; count++) {
        for (size_t i = 0; i < len; i++) {
            /* 计算右边界 */
            size_t j = i + count - 1;
            if (j >= len) {
                /* 右边界越界 */
                break;
            }
            if (count == 1) {
                /* 单个字符的字符串一定是回文字符串 */
                dp[i * len + j] = true;
            }
            else if (count == 2) {
                /* 2个字符的字符串只要相等就是回文字符串 */
                dp[i * len + j] = (s[i] == s[j]);
            }
            else {
                /* 其余情况只要首尾字符相等且去掉首尾的字符串是回文字符串则整体是回文字符串 */
                dp[i * len + j] = (dp[(i + 1) * len + j - 1] && (s[i] == s[j]));
            }
            if (!dp[i * len + j]) {
                continue;
            }
            /* 如果当前子串是回文字符串，记录一下 */
            if (count > maxlen) {
                begin = i;
                maxlen = count;

                //printf("begin: %d maxlen: %d\n", begin, maxlen);
            }
        }
    }

    //printf("dp:\n");
    for (size_t i = 0; i < len; i++)
    {
        std::string s;
        for (size_t j = 0; j < len; j++)
        {
            s += (dp[i * len + j] ? "1" : "0");
        }
        //printf("%s\n", s.c_str());
    }

    delete[] dp;
    return s.substr(begin, maxlen);
}
}
